package _022_2_12

func dfs(min *int, n int, num int) {
	if n == 1 {
		if num < *min {
			*min = num
			return
		}
	}

	if n%2 == 0 {
		dfs(min, n/2, num+1)
	} else {
		dfs(min, n+1, num+1)
		dfs(min, n-1, num+1)
	}
}

func integerReplacement(n int) int {
	min := n
	dfs(&min, n, 0)
	return min
}

type funcStatus struct {
	count        int
	n            int
	statusIsOver bool
	isMinus      bool
}

func integerReplacement2(n int) int {
	min := n
	status := make([]funcStatus, 0)

	f := funcStatus{}
	f.count = 0
	f.statusIsOver = false
	f.n = n

	if f.n%2 != 0 {
		f.isMinus = true
	}
	status = append(status, f)

	for len(status) > 0 {

		tempStatus := status[len(status)-1]

		if tempStatus.n == 1 {

			if tempStatus.count < min {
				min = tempStatus.count
			}
			status = status[:len(status)-1]
			continue
		}

		if !tempStatus.statusIsOver {

			if tempStatus.n%2 == 0 {
				status[len(status)-1].statusIsOver = true

				nextStatus := funcStatus{
					count:   tempStatus.count + 1,
					n:       n / 2,
					isMinus: false,
				}
				status = append(status, nextStatus)
				continue
			}

			if tempStatus.isMinus {
				status[len(status)-1].statusIsOver = true

				nextStatus := funcStatus{
					count:   tempStatus.count + 1,
					n:       n + 1,
					isMinus: false,
				}
				status = append(status, nextStatus)
			}

		} else {
			if tempStatus.isMinus {
				status = status[:len(status)-1]

				nextStatus := funcStatus{
					count:   tempStatus.count + 1,
					n:       n + 1,
					isMinus: false,
				}
				status = append(status, nextStatus)
				continue
			}
		}

		status = status[:len(status)-1]

	}
	return min
}
